package com.algorithm.ch1.cjm2.array;


import com.sun.tools.javac.util.Assert;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 *
 * Created by jieming.chen on 2019-07-18
 */
public class ContainsDuplicate {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        int[] nums1 = {1, 2, 3, 4};
        int[] nums2 = {1, 1, 1, 3, 3, 4, 3, 2, 4, 2};

        Assert.check(containsDuplicate(nums), "1");
        Assert.check(!containsDuplicate(nums1), "2");
        Assert.check(containsDuplicate(nums2), "3");
    }

    // hash法
    private static boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        Set<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            hashSet.add(nums[i]);
        }
        return nums.length != hashSet.size();
    }

    // 朴素查找法，循环不变式，下一次搜索之前，搜索过的整数中没有重复的整数
    private static boolean containsDuplicate1(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    // 先排序，再比较有没有相邻的两个重复元素
    private static boolean containsDuplicate2(int[] nums) {
        int[] numsCopy = Arrays.copyOf(nums, nums.length);
        Arrays.sort(numsCopy);
        for (int i = 0; i < numsCopy.length - 1; i++) {
            if (numsCopy[i] == numsCopy[i+1]) {
                return true;
            }
        }
        return false;
    }

}
